With the rapid increase of digital media (particularly digital images) on the Web, robust image search and retrieval have become an important task of internet search engines. Typically, internet image search exploits text-based annotations to retrieve relevant images responsive to text-based queries. However, in some search engines, image-based queries are enabled. A user can identify a query image for submission to the search engine, and the search engine returns a list of result images that are believed to be similar to the query image.
A common technique for identifying similar images to the query image is to perform a nearest-neighbor search for the query image in a multi-dimensional feature space. Each dimension of the multi-dimensional feature space is defined by one of multiple image features that characterize the similarities between images. For a given query image's feature vector, the goal is to find other images that have the nearest feature vectors according to some distance measure. Over the years, various methods for solving the nearest neighbor search problem have been developed.